package com.zjw.algorithm;

import java.util.Arrays;

/**
 * 一个国家由 n 个编号为 0 到 n - 1 的城市组成。在这个国家里，每两个 城市之间都有一条道路连接。
 * <p>
 * 总共有 m 个编号为 0 到 m - 1 的朋友想在这个国家旅游。他们每一个人的路径都会包含一些城市。每条路径都由一个整数数组表示，每个整数数组表示一个朋友按顺序访问过的城市序列。同一个城市在一条路径中可能 重复 出现，但同一个城市在一条路径中不会连续出现。
 * <p>
 * 给你一个整数 n 和二维数组 paths ，其中 paths[i] 是一个整数数组，表示第 i 个朋友走过的路径，请你返回 每一个 朋友都走过的 最长公共子路径 的长度，如果不存在公共子路径，请你返回 0 。
 * <p>
 * 一个 子路径 指的是一条路径中连续的城市序列。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：n = 5, paths = [[0,1,2,3,4],
 * [2,3,4],
 * [4,0,1,2,3]]
 * 输出：2
 * 解释：最长公共子路径为 [2,3] 。
 * 示例 2：
 * <p>
 * 输入：n = 3, paths = [[0],[1],[2]]
 * 输出：0
 * 解释：三条路径没有公共子路径。
 * 示例 3：
 * <p>
 * 输入：n = 5, paths = [[0,1,2,3,4],
 * [4,3,2,1,0]]
 * 输出：1
 * 解释：最长公共子路径为 [0]，[1]，[2]，[3] 和 [4] 。它们长度都为 1 。
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= n <= 105
 * m == paths.length
 * 2 <= m <= 105
 * sum(paths[i].length) <= 105
 * 0 <= paths[i][j] < n
 * paths[i] 中同一个城市不会连续重复出现。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-common-subpath
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */


/**
 * 给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
 * 输出：3
 * 解释：长度最长的公共子数组是 [3,2,1] 。
 * 示例 2：
 * <p>
 * 输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
 * 输出：5
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= nums1.length, nums2.length <= 1000
 * 0 <= nums1[i], nums2[i] <= 100
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/maximum-length-of-repeated-subarray
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution2 {


//    public static void main(String[] args) {
//        System.out.println(new Solution2().longestCommonSubPath(5, new int[][]{{0, 1, 2, 3, 4}, {2, 3, 4}, {4, 0, 1, 2, 3}}));
//
//        System.out.println(new Solution2().longestCommonSubPath(5, new int[][]{{0, 1, 2, 3, 4}, {2, 3, 4},}));
//        System.out.println(new Solution2().longestCommonSubPath(5, new int[][]{{0, 1, 2, 3, 4}, {4, 3, 2, 1, 0},}));
//        System.out.println(new Solution2().longestCommonSubPath(5, new int[][]{{0}, {1}, {2}, {3},}));
//        System.out.println(new Solution2().longestCommonSubPath(5, new int[][]{{1, 2, 3, 4}, {4, 1, 2, 3}}));
//    }

    private final int[] EMPTY_ARRAY = new int[]{};

    public int longestCommonSubPath(int n, int[][] paths) {
        if (paths.length == 0) {
            return 0;
        }

        if (paths.length == 1) {
            return paths[0].length;
        }


        int[] result = EMPTY_ARRAY;

        for (int i = 2; i < paths.length; i++) {
            result = longestCommonPath(result, paths[i]);

            if (result == EMPTY_ARRAY) {
                return 0;
            }
        }

        return result.length;
    }


    /**
     * 查找最长公共子数组，暴力，超时
     */
    private int[] longestCommonPath(int[] a, int[] b) {
        if (a.length == 0 || b.length == 0) {
            return EMPTY_ARRAY;
        }

        int al = 0;
        int ar = 0;
        int maxLength = 0;
        int recordStart = -1;

        while (al < a.length) {
            ar = al;

            int bl = 0;
            int br = 0;
            boolean counting = false;
            while (bl < b.length) {
                if (!counting) {
                    if (b[bl] == a[al]) {
                        br = bl;
                        ar = al;
                        counting = true;
                    } else {
                        bl++;
                    }
                } else {
                    if (ar >= a.length || br >= b.length) {
                        //max end
                        counting = false;
                        bl++;

                        if (maxLength < br - bl + 1) {
                            maxLength = br - bl + 1;
                            recordStart = bl;
                        }
                        continue;
                    }

                    if (a[ar] == b[br]) {
                        ar++;
                        br++;
                    } else {
                        counting = false;
                        bl++;

                        if (maxLength < br - bl + 1) {
                            maxLength = br - bl + 1;
                            recordStart = bl;
                        }
                    }
                }
            }

            al++;
        }

        if (recordStart == -1) {
            return EMPTY_ARRAY;
        } else {
            return Arrays.copyOfRange(b, recordStart, recordStart + maxLength);
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution2().findLength(
                new int[]{1, 2, 3, 2, 1},
                new int[]{3, 2, 1, 4, 7}
        ));
        System.out.println(new Solution2().findLength(
                new int[]{0, 0, 0, 0, 0},
                new int[]{0, 0, 0, 0, 0}
        ));
    }

    /**
     * 查找公共最长子数组长度
     */
    public int findLength(int[] a, int[] b) {
        return solveMaxLengthSubPath(a, b);
    }

    /**
     * 滑动窗口解法
     */
    private int solveMaxLengthSubPath(int[] a, int[] b) {
        //滑动者
        int[] min = a.length > b.length ? b : a;
        //base
        int[] window = a.length > b.length ? a : b;

        int maxLength = 0;
        int maxLengthStartIndex = 0;

        int pl = -min.length + 1;
        while (pl < window.length) {
            if (pl < 0) {
                maxLength = Math.max(maxLength, computeLength(min, -pl, window, 0, pl + min.length));
            }

            if (pl >= 0 && pl < window.length - min.length) {
                maxLength = Math.max(maxLength, computeLength(min, 0, window, pl, min.length));

                if (maxLength == min.length) {
                    return min.length;
                }
            }

            if (pl >= window.length - min.length) {
                maxLength = Math.max(maxLength, computeLength(min, 0, window, pl, window.length - pl));
            }

            pl++;
        }

        return maxLength;
    }

    private int computeLength(int[] a, int al, int[] b, int bl, int count) {
        int length = 0;
        int temp = 0;
        for (int i = 0; i < count; i++) {
            if (a[al + i] == b[bl + i]) {
                temp++;
            } else {
                temp = 0;
            }
            length = Math.max(temp, length);
        }
        return length;
    }


    /**
     * Hash算法
     */
    private int solveMaxLengthSubPathByHash(int[] a, int[] b) {


        return 0;
    }

}
